package com.Algorithm.Study.ALGStudy;

/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zjz
 * @Date: 2022/03/20/21:23
 * @Description:
 * @Target:
 */
public class 暴力枚举最长递增序列 {

    public static void main(String[] args) {
        // 50位连续的就跑不动了。。。。。。。。

//        int[] ints = new int[]{15,12,13,14,15,16,7,8,9,10,11,12,13,14,15,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41};
//        int[] ints = new int[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49};
//        int[] ints = new int[]{25,34,3,28,40,47,35,38,32,43,45,47,28,19,37,22,41,32,29,32,45,11,32,26,40,14,0,43,0,39,38,0,11,2,12,39,18,3,31,16,33,6,18,49,4,46,9,14,11,15};
        int[] ints = new int[]{3,-4,2,-1,2,6,-3,4,-10,-11,11,12};


        int maxLen = 0;
        int maxLenStartIndex = 0;
        long l = System.currentTimeMillis();
        System.out.println(l);
        int memory[] = new int[ints.length];
/*        for (int i = 0; i < ints.length; i++) {
            if (maxLen<GetAddLen(ints,i,memory)){
                maxLen = GetAddLen(ints,i,memory);
                maxLenStartIndex = i;
            }


        } */


        for (int i = 0; i < ints.length; i++) {
            int maxRes = getMaxRes(ints, i, memory);
            if (maxLen<maxRes){
                maxLen = maxRes;
                maxLenStartIndex = i;
            }

        }

        long l1 = System.currentTimeMillis();
        System.out.println(l1);



//        System.out.println("最长长度："+maxLen+" 下标为："+maxLenStartIndex+"   跑得时间为："+(l1-l));
        System.out.println("最大和："+maxLen+" 下标为："+maxLenStartIndex+"   跑得时间为："+(l1-l));
/*
        for (int anInt : ints) {
            if (anInt>25){
                System.out.print(anInt+" ");
            }
        }
*/
/*
        for (int i = 0; i < 50; i++) {
            System.out.print(i+",");
        }*/
    }




    // 一个递归方法，返回递增序列的长度
    static int  GetAddLen(int[] ints,int index,int[] memory){

        // 加个存储，判断是否有存储
        if (memory[index]!=0){
            return memory[index];
        }
        // 最后一个如果是就是1，不是就不会进来的。
        if (index == ints.length-1){
            return 1;
        }
        // 当前元素就属于序列的一个
        int maxLen = 1;
        for (int i = index+1; i < ints.length; i++) {
            if (ints[i]>ints[index]){
                // 如果后一个大于当前的话，就找这个大于的元素的递增。
                maxLen = Math.max(maxLen,GetAddLen(ints,i,memory)+1);
            }
        }
        memory[index] = maxLen;
        return maxLen;
    }


    // 写下最大连续子序列的值，入参数组，下标，缓存记录
    static int getMaxRes(int[] ints,int index,int[] memory){
        if (index==ints.length-1){
            return ints[index]<=0?0:ints[index];
        }
        // 查缓存记录
        if (memory[index]!=0){
            return memory[index];
        }
        int max = ints[index];  // 最大值
        int sum = ints[index];  // 序列和

        // 如果当前数及后面数之和大于0，表示当前序列还在继续，最大值，序列和分开记录
        if (ints[index]+ints[index+1]>=0){
//            sum += getMaxRes(ints,index+1,memory);
            max = Math.max(max,max+getMaxRes(ints,index+1,memory));
        }else {
            // 如果小于0情况发生，表示这一段序列该结束了。
            return max;
        }

        // 缓存记录
        memory[index] = max;

        return max;
    }


}
